package com.dxb.test.sort;

/**
 * 桶排序
 * 桶排序又叫箱排序，是计数排序的升级版，它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序
 */
public class BucketSort extends BaseSort {
    private int max;
    private int min;

    public BucketSort(int[] array) {
        super(array);
        min = max = array[0];
        for (int i = 1; i < length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
    }

    @Override
    public void sort() {
        //桶数
        int bucketNum = (max - min) / length + 1;
        int[][] bucketArr = new int[bucketNum][length];
        //每个桶可能添加数据的下标
        int[] bucketIndexCounter = new int[bucketNum];
        //将每个元素放入桶
        for (int i = 0; i < length; i++) {
            int num = (array[i] - min) / (length);
            if (bucketArr[num] == null) {
                bucketArr[num] = new int[length];
            }
            bucketArr[num][bucketIndexCounter[num]++] = array[i];
        }
        //对每个桶进行排序
        int srcPos = 0;
        for (int k = 0; k < bucketNum; k++) {
            //插入排序
            for (int i = 1; i < bucketIndexCounter[k]; i++) {
                int current = bucketArr[k][i];
                int j = i - 1;
                while (j >= 0 && bucketArr[k][j] > current) {
                    bucketArr[k][j + 1] = bucketArr[k][j];
                    j--;
                }
                bucketArr[k][j + 1] = current;
            }
            //排序完后，放入原数组
            System.arraycopy(bucketArr[k], 0, array, srcPos, bucketIndexCounter[k]);
            srcPos += bucketIndexCounter[k];
        }

    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        BaseSort qs = new BucketSort(array);
        qs.run();
    }
}
